package com.tucc.hello.leetcode.no1_400.no1_200.no61_80.no69;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        for (int i = 1; i <= 100; i++) {
//            System.out.println(i + " : " + solution.mySqrt(i));
//        }
        System.out.println(solution.mySqrt(2147395599));
    }

    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        long temp1 = 1;
        long temp = temp1;
        while (temp < x && temp > 0) {
            temp1 *= 10;
            temp = temp1 * temp1;
        }
        long left = (int)temp1 / 10;
        long right = (int)temp1;
        while (left < right) {
            long mid = (left + right) / 2;
            long m = mid * mid;
            if (m == x) {
                return (int)mid;
            }
            if (m < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left * left <= x ? (int)left : (int)left - 1;
    }
}
